package com.clstu.huffumancode;

import java.io.*;
import java.util.*;

/**
 * 演示哈夫曼树的利用 ---- 哈夫曼编码
 */
public class HuffManCode {

    static Map<Byte,String> huffmanCodes = new HashMap<>();//存放哈夫曼编码
    static StringBuilder stringBuilder = new StringBuilder();//

    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
//        System.out.println(contentBytes.length);//40个字节
//        //创建哈夫曼树
//        List<Node> nodes = getNodes(contentBytes);
//        Node root = creatHuffmanTree(nodes);
//        //遍历哈夫曼树
////        preOrder(root);
//        //得到哈夫曼编码
//        Map<Byte, String> huffmanCodes = getHuffManCode(root);
//        //查看哈夫曼编码
////        Set<Map.Entry<Byte, String>> entries = huffmanCodes.entrySet();
////        for (Map.Entry<Byte, String> entry : entries) {
////            System.out.println(entry.getKey()+" : "+entry.getValue());
////        }
//        //查看压缩后的结构
//        System.out.println(Arrays.toString(contentBytes));
//        byte[] zip = zip(contentBytes, huffmanCodes);
//        byte[] zip = huffManZip(contentBytes);//压缩后 40字节 -----> 17字节 (压缩率高)
//        System.out.println("原数组:"+Arrays.toString(contentBytes));
//        System.out.println("哈夫曼压缩数组:"+Arrays.toString(zip));
//        System.out.println(zip.length);//17

//        String regStr = byteToBitString(zip);
//        System.out.println("解码编码:"+regStr);
//        byte[] decode = decode(zip,huffmanCodes);
//        System.out.println("解码后的字符串:"+new String(decode));

        //测试哈夫曼编码对文件的压缩和解压(对已经压缩过的文件不会有压缩的效果,比如很多二进制文件)
        zipFile("D:\\xx.txt","D:\\xx.zip");
        unZipFile("d:\\xx.zip","d:\\xxx.txt");//结果,字符重复率越高,压缩率就越高

    }

    //编写方法,实现文件的压缩,(传入源路径和目的路径)
    public static void zipFile(String scr,String dest){
        FileInputStream fileInputStream = null;
        ObjectOutputStream oos = null;
        try {
            //读入文件到字节数组
            //创建对应大小的字节数组
            byte[] data = new byte[(int) new File(scr).length()];
            fileInputStream = new FileInputStream(scr);
            //read方法从输入流读文件到字节数组
            fileInputStream.read(data);
            //压缩
            byte[] zipBytes = huffManZip(data);
            //得到哈夫曼编码规则
            Map<Byte, String> huffmanCodes = getHuffmanCodes(data);
            //将压缩数组和编码规则都通过对象流写入文件,方便读取(序列化)
            oos = new ObjectOutputStream(new FileOutputStream(dest));
            oos.writeObject(zipBytes);
            oos.writeObject(huffmanCodes);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            //关闭资源
            try {
                if(fileInputStream!=null) fileInputStream.close();
                if (oos!=null) oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    //编写方法,解压文件
    public static void unZipFile(String src,String dst){
        ObjectInputStream ois = null;
        FileOutputStream fileOutputStream = null;
        try {
            //读取文件,反序列化,得到压缩后的字节数组和编码规则
            ois = new ObjectInputStream(new FileInputStream(src));
            byte[] zipBytes =(byte[]) ois.readObject();
            Map<Byte,String> huffmanCodes = (Map<Byte,String>) ois.readObject();
            //解码,得到解码后的字节数组
            byte[] bytes = decode(zipBytes, huffmanCodes);
            //写入到目的路径
            fileOutputStream = new FileOutputStream(dst);
            fileOutputStream.write(bytes);
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        } finally {
            try {
                //关闭资源
                if(ois!=null) ois.close();
                if(fileOutputStream!=null) fileOutputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    //方法重置,方便调用
    public static byte[] decode(byte[] zip,Map<Byte,String> huffmanCodes){
        String regStr = byteToBitString(zip);
        return decode(regStr,huffmanCodes);
    }

    //编写方法,根据哈夫曼编码规则解码,返回解码后的字节数组
    public static byte[] decode(String zipString,Map<Byte,String> huffmanCodes){
        //先反转map,得到解码规则
        Map<String, Byte> decodes = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            decodes.put(entry.getValue(),entry.getKey());
        }
        //不断扫描传入的哈夫曼字符串,匹配一个解码一个,放到ArrayList中
        ArrayList<Byte> bytes = new ArrayList<>();
        for (int i = 0; i < zipString.length();) {
            int count = 0;
            Byte b = null;
            while (true){
                //如果到最后
                if(i+count == zipString.length()-1){
                    break;
                }
                b = decodes.get(zipString.substring(i,i+(++count)));
                //如果扫描到
                if(b != null){
                    break;
                }
            }
            //存入bytes
            bytes.add(b);
            //i后移
            i = i+count;
            //如果到最后
            if(i+count == zipString.length()-1){
                break;
            }
        }
        //将ArrayList中的字节导入到字节数组中返回
        byte[] res = new byte[bytes.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = bytes.get(i);
        }
        return res;
    }

    //编写方法,将压缩后的字节数组转成01字符串返回
    public static String byteToBitString(byte[] bs){
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0;i<bs.length;i++) {
            //注意,如果byte中存放的数是正数且很小,转成int之后前面的0会被省略掉
            //需要 | 256(即1 0000 0000)来使被抹掉的0都显示出来
            //前面的byte中的8个bit的每一位都是有用的,所以需要补0,(不能被省略掉!)
            //还需要注意,最后一个字节的存储并不是按照8bit都有效存入,
            // 可能原本就没有8bit,于是不需要补0
            // (比如最后只有5位 11100(原本的编码)---(存入)-->00011100----(取出)--->不补0(11100),补0(00011100))
            int temp = bs[i];
            //toBinaryString(),输出的是数的补码,负数前面补1,直到32位,正数前面的0直接省略
            //注意,如果byte中存放的数是正数且很小,转成int之后前面的0会被省略掉
            //需要 | 256(即1 0000 0000)来使被省略的0都显示出来
            //如果不是最后一字节
            if(i != bs.length-1) {
                temp |= 256;//补0(如果需要)
                String str = Integer.toBinaryString(temp);
                stringBuilder.append(str.substring(str.length()-8));
            }else {
                //如果是最后一个字节
                String str = Integer.toBinaryString(temp);
                //<0说明8位都有效
                if(temp<0) {
                    stringBuilder.append(str.substring(str.length()-8));
                }else {
                    stringBuilder.append(str);
                }
            }
        }
        return stringBuilder.toString();
    }

    //编写方法,得到字节数组对应的哈夫曼编码表
    public static Map<Byte,String> getHuffmanCodes(byte[] contentBytes){
        //1.统计个数,
        List<Node> nodes = getNodes(contentBytes);
        //2.根据各个字符的个数创建哈夫曼数
        Node root = creatHuffmanTree(nodes);
        //3.根据哈夫曼树生成哈夫曼编码
        return getHuffManCode(root);
    }

    //将所有的方法封装到一起,直接一个方法实现哈夫曼压缩,便于调用
    public static byte[] huffManZip(byte[] contentBytes){
        //1.统计个数,
        List<Node> nodes = getNodes(contentBytes);
        //2.根据各个字符的个数创建哈夫曼数
        Node root = creatHuffmanTree(nodes);
        //3.根据哈夫曼树生成哈夫曼编码
        Map<Byte, String> huffmanCodes = getHuffManCode(root);
        //4.根据哈夫曼编码压缩,
        byte[] zip = zip(contentBytes, huffmanCodes);
        //5.返回压缩后的结果
        return zip;
    }

    //编写方法,根据哈夫曼编码,将传进来的字节数据编码后返回,同样返回字节数组(在机器中是以二进制补码的方式存储的)
    private static byte[] zip(byte[] bytes,Map<Byte,String> huffCodes){
        //根据哈夫曼编码,将字节数组转成它的哈夫曼编码的字符串形式
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b: bytes) {
            stringBuilder.append(huffCodes.get(b));
//            System.out.print(huffmanCodes.get(b)+" ");
        }
//        System.out.println("存入编码:"+stringBuilder);
//        System.out.println("哈夫曼编码的bit数:"+stringBuilder.length());
        //得到长度创建新的字节数组
        int len = (stringBuilder.length()+7)/8;//+7的原因是保证数组刚好够
        byte[] zBytes = new byte[len];
        //循环经字符串转换压缩进字符数组中,实现真正的压缩
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            if(i+8<stringBuilder.length()){
                //没到结尾(预防空指针异常)                            //二进制存储,不是默认的十进制
                zBytes[i/8] = (byte) Integer.parseInt(stringBuilder.substring(i,i+8),2);
            }else {
                //结尾(仍然可能会有精度损失,比如 01和0001存入之后都是 0000 0001,解码的时候无法确定最后一位!!)
                zBytes[i/8] = (byte) Integer.parseInt(stringBuilder.substring(i),2);//注意二进制,
            }
        }
        //返回压缩后的字节数组
        return zBytes;
    }

    //编写方法,根据传入的字节数据,根据该字节和它出现的次数新建Node节点放到ArrayList中返回
    private static List<Node> getNodes(byte[] bytes){
        //用hashMap来统计个数
        HashMap<Byte, Integer> byteWightMap = new HashMap<>();
        for (byte b : bytes) {
            Integer count = byteWightMap.get(b);
            if(count == null){
                byteWightMap.put(b,1);
            }else {
                byteWightMap.put(b,count+1);
            }
        }
        //遍历map,存入ArrayList中
        ArrayList<Node> nodes = new ArrayList<>();
        Set<Map.Entry<Byte, Integer>> entries = byteWightMap.entrySet();
        for (Map.Entry<Byte, Integer> entry : entries) {
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    //编写方法,根据传入的ArrayList创建哈夫曼树并返回
    private static Node creatHuffmanTree(List<Node> nodes){
        while (nodes.size()>1){
            //每一轮都要排序
            Collections.sort(nodes);
            //取出两个最小的组成二叉树将新生成的父节点再放回去
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        //最后nodes中只剩下哈夫曼树的根节点
        return nodes.get(0);
    }

    //编写方法,根据哈夫曼树生成对应的哈夫曼编码(先序遍历)
    public static void getHuffManCode(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //拼接传入的哈夫曼编码
        stringBuilder1.append(code);
        //左右递归
        //如果不是叶子节点
        if(node.data == null){
            getHuffManCode(node.left,"0",stringBuilder1);
            getHuffManCode(node.right,"1",stringBuilder1);
        }else {
            //否则就是是叶子节点(说明一个字符的哈夫曼编码已经形成,加入到map中)
            huffmanCodes.put(node.data,stringBuilder1.toString());
        }
    }

    //为了调用方便,重载编码的方法
    public static Map<Byte,String> getHuffManCode(Node node){
        getHuffManCode(node,"",stringBuilder);
        return huffmanCodes;
    }

    //编写方法,前序遍历哈夫曼树
    public static void preOrder(Node root){
        //如果树空
        if(root == null){
            System.out.println("二叉树空");
        }else {
            root.preOrder();
        }
    }

    //测试转换过程,确实可能会有损失,01或者0001 存进字节数组之后都是1,还原时不能确定是01还是0001
    public static void test(){
        int b = Integer.parseInt("00101010",2);//最前面的0被省略(正数),不满8位默认前面是0然后省略
        String str = Integer.toBinaryString(b);
        if (b<0){
            str = str.substring(str.length()-8);
        }
        System.out.println("\n"+str);
    }

}
/**
 * 创建Node, 存数据和权值
 */
class Node implements Comparable<Node>{
    Byte data;//存放字符本身 如'a' => 97 ..
    int weight;//存放该字符出现的次数
    Node left;
    Node right;

    //构造器
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //编写方法,前序遍历二叉树
    public void preOrder(){
        //前序遍历: 自己 -----> 左递归 -------> 右递归
        System.out.println(this);
        if(left!=null){
            left.preOrder();
        }
        if(right!=null){
            right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序,this在前,小到大
        return this.weight - o.weight;
    }
}